#include "SqBiTree.h"

/*
insertNode:往一棵二叉排序树中加入一个元素,使得二叉树任然具有排序性
@root:指针,你要把元素加入到哪一棵树
@x:你要加入的元素的值
返回值:
返回加入元素后的二叉树的根节点的地址
*/
BiTNode *insertNode(BiTNode *root,Datatype x)
{
    //为插入的数据开辟一个空间
    BiTNode *pt = (BiTNode *)malloc(sizeof(*pt));
    pt->data = x;
    pt->lchild = pt->rchild = NULL;


    if(root == NULL)
    {
        root = pt;  //新创建的节点成为空树的根节点
    }
    else
    {
        //2.找一个插入位置,新节点成为查找路径上面最后一个节点的左子节点或者右子节点
        BiTNode *p = root;  //从根节点开始找一个位置
        BiTNode *pr = p;    //记录查找路径上的最后一个节点
        while(p !=NULL)
        {
            if(p->data < pt->data)//新节点比当前节点大,需要放到当前节点的右子树中
            {
                pr = p;
                p = p->rchild;
            }
            else if(p->data > pt->data)//新节点比当前节点小,需要放到当前节点的左子树中
            {
                 pr = p;
                p = p->lchild;

            }
            else//相同节点,不处理
            {
                free(pt);
                return root;;
            }
        }
        //循环结束.p肯定是指向了NULL,查找路径的最后一个节点就是p的父节点(pr)
        //pt就是要放到p结束的位置,pt要么成为pr的左子节点要么成为pr的右子节点
        //3.分情况插入操作
        if(pr->data < pt->data)
        {
            pr->rchild = pt;
        }
        else if(pr->data > pt->data)
        {
            pr->lchild = pt;
        }
    }
    return root;
}

/*
pre_order:以先序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/
void pre_order(BiTNode *tree)
{
    if(tree == NULL)
    {
        return;
    }
    //1.先访问根节点
    printf("%c",tree->data);
    //2.再按照同用的方法(先根遍历)去访问根节点的左子树
    pre_order(tree->lchild);
    //3.再按照同用的方法(先根遍历)去访问根节点的右子树
    pre_order(tree->rchild);
}

/*
mid_order:以中序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/
void mid_order(BiTNode *tree)
{
    if(tree == NULL)
    {
        return;
    }
    //1.先按照中序遍历的方法去访问根节点的左子树
    mid_order(tree->lchild);
    //2.再访问根节点
    printf("%c",tree->data);
    //3.再按照中序遍历的方法去访问根节点的右子树
    mid_order(tree->rchild);
}

/*
last_order:以后序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/
void last_order(BiTNode *tree)
{
    if(tree == NULL)
    {
        return;
    }
    //1.先按照后序遍历的方法去访问根节点的左子树
    last_order(tree->lchild);
    //3.再按照后序遍历的方法去访问根节点的右子树
    last_order(tree->rchild);
    //2.再访问根节点
    printf("%c",tree->data);
}

/*
ceng_order:以层次遍历的方法访问tree指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/
void level_order(BiTNode *tree)
{
    if(tree == NULL)
    {
        return;
    }
    //创建一个队列
    LkQueue *t = InitQueue();
    //BiTNode *pnew = tree;
    //树有节点，值
    //根节点的入队
    EnQueue(t,tree);

    //循环（队头不为空）
    while(!QueueIsEmpty(t))
    {
        int v;
        BiTNode *pnew = dequeue(t);//保存队头的值，队头出队，
        printf("%c",pnew->data);//打印队头的值

        //访问队列的队头（节点）
        if(pnew->lchild != NULL)//有左右子节点，将左右子节点入队
        {
            EnQueue(t,pnew->lchild);
        }
        if(pnew->rchild != NULL)
        {
            EnQueue(t,pnew->rchild);
        }
        //没有，不管
    }
     //销毁
    DestoryQueue(t);
}

//打印二叉树的4种遍历方式
void orderTree(BiTNode *tree)
{
    printf("先序遍历:");
    pre_order(tree);   
    printf("\n");

    printf("中序遍历:");
    mid_order(tree);   
    printf("\n");

    printf("后序遍历:");
    last_order(tree);   
    printf("\n");

    printf("层次遍历:");
    level_order(tree);   
    //level_order2(tree);
}

/*
high_tree:求树的高度
@tree:指针,指向你要遍历的二叉树的根节点
返回值:无
*/
int high_tree(BiTNode *tree)
{
    /*
    根据上面遍历二叉树的思路,写一个代码,计算二叉树的高度(使用递归即可)
        提示:
        如果二叉树为空,高度就是0
        如果不为空,二叉树的高度是左子树高度和右子树高度中大的那一个加1
    */
   if(tree == NULL)
   {
    return 0;
   }
   //用递归计算左子树高度
   int leftHight = high_tree(tree->lchild);
   //用递归计算右子树高度
   int rightHight = high_tree(tree->rchild);
   //当前树的高度为左右子树的高度的最大值+1
   return (leftHight > rightHight ? leftHight : rightHight + 1);
}

/*删除一个节点*/

BiTNode *Delete_x_root(BiTNode *tree,Datatype x)
{
    BiTNode *px = tree;
    BiTNode *pr = tree;
    while(px != NULL)
    {
        if(px->data > x)
        {
            pr = px;//记录px的父节点
            px = px->lchild;
        }
        else if(px->data < x)
        {
            pr = px;//记录px的父节点
            px = px->rchild;
        }
        else
        {
            break;//循环退出
        }
    }
    if(px == NULL)
    {
        printf("不存在节点\n");
        return tree;
    }
    //px是叶子节点
    if(px->lchild == NULL && px->rchild == NULL)//段错误
    {
        if(px == tree)
        {
            tree = NULL;
        }
        else if(px == pr->lchild)//px是左子节点
        {
            pr->lchild = NULL;
        }
        else//px是右子节点
        {
            pr->rchild = NULL;
        }
        free(px);
        //return tree;
    }
    //px不是叶子节点，但只有一个节点
    else if(px->rchild == NULL)
    {
        if(px == tree)
        {
            tree = px->lchild;
        }
        else
        {
            //考虑待删除的节点是pr的左还是右
            if(px == pr->lchild)//要删除的px是pr的左子节点
            {
                pr->lchild = px->lchild;
                //px->rchild =NULL;
            }
            else
            {
                pr->rchild = px->lchild;
                
            }
        }
        px->rchild =NULL;
        free(px);
        //return tree;
    }
    else if(px->lchild == NULL )
    {
        if(px == tree)
        {
            tree = px->rchild;
        }
        else
        {
             if(px == pr->rchild)//要删除的px是pr的左子节点
            {
                pr->rchild = px->rchild;
                //px->rchild =NULL;
            }
            else
            {
                pr->lchild = px->rchild;
                //
            }
        }
        px->rchild =NULL;
        free(px);
        //return tree;
    }
    //px的左右子节点都存在
    else if(px->lchild && px->rchild)
    {
        //找一个合适的节点的值和px交换
        /*
        //左边找，找最大值，先左转，在一直右转到头
        BiTNode *p = px->lchild;
        while(p)
        {

            if(p->lchild == NULL && p->rchild == NULL)
            {
                //交换
                px->data = p->data;
                free(p);
            }
            else if(p->rchild == NULL)
            {
                BiTNode *q = p->lchild;//定义一个q，万一p的左节点后面还有一堆左节点
                px->data = p->data;//将p的数据给px
                p->data = q->data;//p的数据变成p->lchild
                p->lchild = q->lchild;//跳过p，指向p的下一个
                free(q);//删除原来的q的下一个
            }
            p = px->rchild;
        }
        */
        //或者右边找，找最小值，先右转一个，在一直左转
        BiTNode *p = px;
        pr = px;
        px = px->rchild;
        while(px->lchild)
        {
            pr = px;
            px = px->lchild; 
        }
        Datatype tmp = p->data;
        p->data = px->data;
        px->data = tmp;
        //return tree;
        //再将拿到的值与数据域交换，删除要删除的
    }
    return tree;
}



/*单向右旋平衡处理*/
BiTNode *SingleRotateWith(BiTNode *tree)
{
    
}





/*
InitQueue:初始化一个队列
返回值:返回创建好的队列的地址
*/
LkQueue *InitQueue()
{
    //分配链表队列空间
    LkQueue *q = (LkQueue *)malloc(sizeof(LkQueue));
    //空间初始化
    q->front = 0;
    q->rear = 0;
    q->num = 0;
    return q;
}

/*
DestoryQueue:销毁一个队列
@q:你要销毁的队列的地址
返回值:无
*/
void DestoryQueue(LkQueue *q)
{
    if(q)
    {
        ClearQueue(q);
        free(q);
    }
}

/*
ClearQueue :清空一个队列(把队列中的数据元素都清空)
@q:你要清空的队列的地址
返回值:无
*/
void ClearQueue(LkQueue *q)
{
    if(q == NULL || q->front ==NULL)
    {
        return;
    }
    while(!QueueIsEmpty(q))
    {
        DeQueue(q);
    }
}

/*
QueueIsEmqty:判断队列是否为空(是否存在用户数据)
@q:你要操作的队列的地址
返回值:
    返回true表示队列为空
    返回false表示队列不为空
*/
bool QueueIsEmpty(LkQueue *q)
{
    return q == NULL || q->num == 0;
}

/*
QueueSize:获取队列的大小(用户元素的个数)
@q:你要操作的队列的地址
返回值:
返回队列中当前的元素个数
*/
int QueueSize(LkQueue *q)
{
     return q == NULL? 0:q->num;
}

/*
GetHead:获取队头元素(下一次出队的元素),但是不出队列
@q:你要操作的队列的地址
@v:指针,指向一块可用的空间,用来保存队头数据的值
返回值:
    返回true表示获取成功
    返回false表示获取失败
*/
bool GetHead(LkQueue *q,BiTNode *v)
{
    if(QueueIsEmpty(q))
    {
        return false;
    }
    //把对头元素存放到
    v = q->front->data;
    return true;
}

/*
EnQueue(qush):入队列,把一个用户数据存放到队列中去(放到队尾)
@q:你要操作的队列的地址
@value:你要入队的数据
返回值:
    返回true表示入队成功
    返回false表示入队失败
*/
bool EnQueue(LkQueue *q,BiTNode *value)
{
    //分配一个节点空间
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = value;
    p->next = NULL;
    p->prev = NULL;
    if(q->front == NULL)
    {
        q->front = q->rear = p;
        q->num++;
    }
    else
    {
        q->rear->next = p;
        p->next = q->rear;
        q->rear = p;
        q->num++;
    }
    return true;
}

/*
DeQueue(qoq):出队列,把一个用户数据从队列中拿出来(去掉队头)
@q:你要操作的队列的地址
返回值:
    返回true表示出队成功
    返回false表示出队失败
*/
bool DeQueue(LkQueue *q)
{
    if(QueueIsEmpty(q))
    {
        return false;
    }
    Node *p = q->front;
    if(q->front == q->rear)
    {
        q->front = q->rear = NULL;
    }
    else
    {
        q->front = p->next;
        q->front->prev = NULL;
        p->next = NULL;
    }
    free(p);
    q->num--;
    return true;
}


// dequeue  保存队头，出队
BiTNode* dequeue(LkQueue *q)
{
    if (q->front == NULL)
    {
       return NULL;
    }

    Node *temp = q->front;
    BiTNode *node = temp->data;//保存队头

    if (q->front == q->rear)
    q->front = q->rear = NULL;
    else
    {
        q->front = q->front->next;
        q->front->prev = NULL;
        temp->next = NULL;
    }

    free(temp);
    q->num--;
    return node;
}


